package com.hfb.mashibing.alip8.diamondsquarealgorithm.class00;

import java.util.Arrays;

/**
 * 题目：在一个无需数组中，求第k小的数
 *
 * BFPRT算法解决的问题十分经典，
 * 即从某n个元素的序列中选出第k大（第k小）的元素，
 * 通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。
 * 该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，
 * 依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。
 *
 * 思路，快排算法：
 * 利用快速排序的思路，选取一个划分值，小于这个数的放右边，等于这个数的放中间，大于这个数的放右边
 *
 * 算法步骤：
 * 1. 将n个元素每5个一组，分成n/5(上界)组。
 * 2. 取出每一组的中位数，任意排序方法，比如插入排序。
 * 3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
 * 4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
 * 5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
 * 终止条件：n=1时，返回的即是i小元素。
 *
 *
 * 时间复杂度：o(n)
 *
 */
public class Code05_Bfprt {
    public static int[] partition(int[] arr, int L, int R, int p) {
        int less = L - 1;
        int more = R + 1;
        while(L < more) {
            if(arr[L] < p) {
                swap(arr, ++less, L++);
            } else if (arr[L] > p) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        return new int[] { less + 1, more - 1 };
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 9, 7, 6, 1, 4, 5};
        int k = 4;
        System.err.println(Arrays.toString(
            partition(arr, 0, arr.length-1, k)));
    }

}
